/*
 * Albareth - an action roleplaying game.
 * Copyright (C) 2008 Jens Anuth
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 *   02110-1301, USA.
 * 
 * $Id: SimplePathfinder.java 35 2008-05-05 14:16:37Z jens464 $
*/
package albareth.util;

import frosch.util.Direction;

/**
 * A simple, naive, but fast table-based pathfinding method, that just fits the
 * needs of the game. It's stateless.
 */
public class SimplePathfinder implements Pathfinder
{
    private static SimplePathfinder _instance = null;
    
    private SimplePathfinder()
    {
    }
    
    public static SimplePathfinder getInstance()
    {
        if (_instance == null) {
            _instance = new SimplePathfinder();
        }
        return _instance;
    }

    public int getNextStep(Location from, Location to)
    {
        int[] sequence = getDirSequence(from.x, from.y, to.x, to.y);
        
        for (int i = 0; i < sequence.length; i++) {
            Location neighbor = from.getNeighborLocation(sequence[i]);
            if (!neighbor.isBlocked()) {
                return sequence[i];
            }
        }
        return Direction.NOWHERE; //all blocked
    }
    
    
    /**
     * Get a best-first sorted sequence of directions
     * this owner should try to walk into,
     * when it wishes to reach the given location.
     * Based on a pre-made table.
     */
    private int[] getDirSequence(int fromX, int fromY, int toX, int toY)
    {
        int[] sequence = new int[8];
        int dx = toX - fromX;
        int dy = toY - fromY;
        int dxAbs = Math.abs(dx);
        int dyAbs = Math.abs(dy);

        if (dy < 0 && dyAbs >= 2*dxAbs) {
            sequence[0] = Direction.NORTH;
            if (dx < 0) {
                sequence[1] = Direction.NORTH|Direction.WEST;
                sequence[2] = Direction.NORTH|Direction.EAST;
                sequence[3] = Direction.WEST;
                sequence[4] = Direction.EAST;
                sequence[5] = Direction.SOUTH|Direction.WEST;
                sequence[6] = Direction.SOUTH|Direction.EAST;
            } else {
                sequence[1] = Direction.NORTH|Direction.EAST;
                sequence[2] = Direction.NORTH|Direction.WEST;
                sequence[3] = Direction.EAST;
                sequence[4] = Direction.WEST;
                sequence[5] = Direction.SOUTH|Direction.EAST;
                sequence[6] = Direction.SOUTH|Direction.WEST;
            }
            sequence[7] = Direction.SOUTH;

        } else if (dx < 0 && dy < 0 && dyAbs < 2*dxAbs  && dxAbs < 2*dyAbs ) {
            sequence[0] = Direction.NORTH|Direction.WEST;
            if (dxAbs > dyAbs) {
                sequence[1] = Direction.WEST;
                sequence[2] = Direction.NORTH;
                sequence[3] = Direction.SOUTH|Direction.WEST;
                sequence[4] = Direction.NORTH|Direction.EAST;
                sequence[5] = Direction.SOUTH;
                sequence[6] = Direction.EAST;
            } else {
                sequence[1] = Direction.NORTH;
                sequence[2] = Direction.WEST;
                sequence[3] = Direction.NORTH|Direction.EAST;
                sequence[4] = Direction.SOUTH|Direction.WEST;
                sequence[5] = Direction.EAST;
                sequence[6] = Direction.SOUTH;
            }
            sequence[7] = Direction.SOUTH|Direction.EAST;

        } else if (dx < 0           && dxAbs >= 2*dyAbs ) {
            sequence[0] = Direction.WEST;
            if (dy < 0) {
                sequence[1] = Direction.NORTH|Direction.WEST;
                sequence[2] = Direction.SOUTH|Direction.WEST;
                sequence[3] = Direction.NORTH;
                sequence[4] = Direction.SOUTH;
                sequence[5] = Direction.NORTH|Direction.EAST;
                sequence[6] = Direction.SOUTH|Direction.EAST;
            } else {
                sequence[1] = Direction.SOUTH|Direction.WEST;
                sequence[2] = Direction.NORTH|Direction.WEST;
                sequence[3] = Direction.SOUTH;
                sequence[4] = Direction.NORTH;
                sequence[5] = Direction.SOUTH|Direction.EAST;
                sequence[6] = Direction.NORTH|Direction.EAST;
            }
            sequence[7] = Direction.EAST;

        } else if (dx < 0 && dy >= 0 && dyAbs < 2*dxAbs  && dxAbs < 2*dyAbs ) {
            sequence[0] = Direction.SOUTH|Direction.WEST;
            if (dxAbs > dyAbs) {
                sequence[1] = Direction.WEST;
                sequence[2] = Direction.SOUTH;
                sequence[3] = Direction.NORTH|Direction.WEST;
                sequence[4] = Direction.SOUTH|Direction.EAST;
                sequence[5] = Direction.NORTH;
                sequence[6] = Direction.EAST;
            } else {
                sequence[1] = Direction.SOUTH;
                sequence[2] = Direction.WEST;
                sequence[3] = Direction.SOUTH|Direction.EAST;
                sequence[4] = Direction.NORTH|Direction.WEST;
                sequence[5] = Direction.EAST;
                sequence[6] = Direction.NORTH;
            }
            sequence[7] = Direction.NORTH|Direction.EAST;

        } else if (          dy >= 0 && dyAbs >= 2*dxAbs) {
            sequence[0] = Direction.SOUTH;
            if (dx < 0) {
                sequence[1] = Direction.SOUTH|Direction.WEST;
                sequence[2] = Direction.SOUTH|Direction.EAST;
                sequence[3] = Direction.WEST;
                sequence[4] = Direction.EAST;
                sequence[5] = Direction.NORTH|Direction.WEST;
                sequence[6] = Direction.NORTH|Direction.EAST;
            } else {
                sequence[1] = Direction.SOUTH|Direction.EAST;
                sequence[2] = Direction.SOUTH|Direction.WEST;
                sequence[3] = Direction.EAST;
                sequence[4] = Direction.WEST;
                sequence[5] = Direction.NORTH|Direction.EAST;
                sequence[6] = Direction.NORTH|Direction.WEST;
            }
            sequence[7] = Direction.NORTH;

        } else if (dx >= 0 && dy >= 0 && dyAbs < 2*dxAbs  && dxAbs < 2*dyAbs ) {
            sequence[0] = Direction.SOUTH|Direction.EAST;
            if (dxAbs > dyAbs) {
                sequence[1] = Direction.EAST;
                sequence[2] = Direction.SOUTH;
                sequence[3] = Direction.NORTH|Direction.EAST;
                sequence[4] = Direction.SOUTH|Direction.WEST;
                sequence[5] = Direction.NORTH;
                sequence[6] = Direction.WEST;
            } else {
                sequence[1] = Direction.SOUTH;
                sequence[2] = Direction.EAST;
                sequence[3] = Direction.SOUTH|Direction.WEST;
                sequence[4] = Direction.NORTH|Direction.EAST;
                sequence[5] = Direction.WEST;
                sequence[6] = Direction.NORTH;
            }
            sequence[7] = Direction.NORTH|Direction.WEST;

        } else if (dx >= 0            && dxAbs >= 2*dyAbs ) {
            sequence[0] = Direction.EAST;
            if (dy < 0) {
                sequence[1] = Direction.NORTH|Direction.EAST;
                sequence[2] = Direction.SOUTH|Direction.EAST;
                sequence[3] = Direction.NORTH;
                sequence[4] = Direction.SOUTH;
                sequence[5] = Direction.NORTH|Direction.WEST;
                sequence[6] = Direction.SOUTH|Direction.WEST;
            } else {
                sequence[1] = Direction.SOUTH|Direction.EAST;
                sequence[2] = Direction.NORTH|Direction.EAST;
                sequence[3] = Direction.SOUTH;
                sequence[4] = Direction.NORTH;
                sequence[5] = Direction.SOUTH|Direction.WEST;
                sequence[6] = Direction.NORTH|Direction.WEST;
            }
            sequence[7] = Direction.WEST;

        } else if (dx >= 0 && dy < 0 && dyAbs < 2*dxAbs  && dxAbs < 2*dyAbs ) {
            sequence[0] = Direction.NORTH|Direction.EAST;
            if (dxAbs > dyAbs) {
                sequence[1] = Direction.EAST;
                sequence[2] = Direction.NORTH;
                sequence[3] = Direction.SOUTH|Direction.EAST;
                sequence[4] = Direction.NORTH|Direction.WEST;
                sequence[5] = Direction.SOUTH;
                sequence[6] = Direction.WEST;
            } else {
                sequence[1] = Direction.NORTH;
                sequence[2] = Direction.EAST;
                sequence[3] = Direction.NORTH|Direction.WEST;
                sequence[4] = Direction.SOUTH|Direction.EAST;
                sequence[5] = Direction.WEST;
                sequence[6] = Direction.SOUTH;
            }
            sequence[7] = Direction.SOUTH|Direction.WEST;

        } else {
            throw new RuntimeException(
                    "This should never happen, but it did with parameters: " +
                    "fromX: " + fromX + " fromY: " + fromY +
                    " toX: " + toX + " toY: " + toY);
        }
        
        return sequence;
    }
    

}
